#include <bits/stdc++.h>

using namespace std;
int n, res;
const int N = 60;

int up[N], down[N], a[N];

void dfs(int num, int uppos, int downpos)
{
    if (uppos + downpos >= n)
        return;
    if (num == n)
    {
        res = min(res, uppos + downpos);
        cout << res << " ";
        return;
    }
    // 枚举放到上升
    int k = 0;
    while (k < uppos && a[num] <= up[k])
    {
        k++;
    }
    if (k == uppos)
    {
        up[k] = a[num];
        dfs(num + 1, uppos + 1, downpos);
    }
    else
    {
        int t = up[k];
        up[k] = a[num];
        dfs(num + 1, uppos, downpos);
        up[k] = t;
    }

    k = 0;
    while (k < downpos && a[num] >= down[k])
    {
        k++;
    }
    if (k == downpos)
    {
        down[k] = a[num];
        dfs(num + 1, uppos, downpos + 1);
    }
    else
    {
        int t = down[k];
        down[k] = a[num];
        dfs(num + 1, uppos, downpos);
        down[k] = t;
    }
}

int main()
{
    while (cin >> n, n)
    {
        res = n;
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
        }
        dfs(0, 0, 0);
        cout << res << endl;
    }
}